Матч 422, Рождественский пирог (BirthdayCake)

Дивизион 2, Уровень 3

На день рождения Вы приготовили праздничный торт. Имеющиеся в наличии фрукты описываются в массиве availableFruits. Для начинки торта необходимо выбрать как минимум k из них. Элемент массива friendsDislikings[i] описывает набор фруктов, который не нравится i - ому Вашему другу. Если в торте будет присутствовать хотя бы один фрукт из friendsDislikings[i], то i - ый Ваше друг торт есть не будет.

Вернуть наибольшее количество друзей, которое может съесть торт, если его обязательно следует начинить как минимум k различными фруктами.

Класс: BirthdayCake

Метод: int howManyFriends(vector<string> availableFruits,

vector<string> friendsDislikings, int k)

Ограничения: availableFruits содержит от 1 до 50 элементов, availableFruits[i] содержит от 1 до 50 символов ‘a’ – ‘z’, friendsDislikings содержит от 1 до 20 элементов, friendsDislikings[i] содержит от 1 до 50 символов, названия фруктов в каждом friendsDislikings[i] разные, ‘a’ – ‘z’, 1 £ k £ количество элементов в availableFruits.

Вход. Массив availableFruits содержит имеющиеся в наличии фрукты, массив friendsDislikings описывает фрукты, которые не нравятся Вашим друзьям, натуральное число k.

Выход. Наибольшее количество друзей, которое может съесть торт, если его обязательно следует начинить как минимум k различными фруктами.

Пример входа

availableFruits	friendsDislikings	k
{"apple", "orange", "strawberry", "cherry"}	{"apple orange", "apple cherry", "strawberry orange", "cherry", "apple"}	2
{"strawberry", "orange", "apple", "lemon", "watermelon"}	{"orange", "apple", "lemon", "watermelon"}	1
{"apple", "orange"}	{"strawberry"}	2

Пример выхода

3

4

1

РЕШЕНИЕ

перебор, маски подмножеств

Простое решение состоит в том, чтобы перебрать все возможные подмножества из k ингредиентов и для каждого из которых вычислить количество людей, которое может съесть торт. Наибольшее количество людей, способных съесть торт из k ингредиентов и будет искомым. Однако имеющихся в наличии фруктов может быть 50, а значение k может равняться, например, 25. Количество подмножеств в этом случае достаточно велико.

Рассмотрим задачу с другой стороны. У нас имеется не более 20 друзей. Рассмотрим все подмножества друзей, для каждого из которых построим множество плохих фруктов (фрукт считается плохим, если его не любит хотя бы один друг из текущего множества друзей). Удалим подмножества друзей, для которых число хороших фруктов строго меньше k. Вернем мощность наибольшего из оставшихся множеств (наибольшее количество друзей, которое может съесть торт, содержащий как минимум k фруктов).

Рассмотрим элементы реализации, позволяющей уложиться во время. Перенумеруем фрукты, заданные в массиве availableFruits. Каждому фрукту поставим в соответствие целое число, создав отображение FruitCode. Для каждого друга построим маску из фруктов, которые ему не нравятся. Если другу не нравится фрукт temp, то соответствующая этому другу маска будет содержать единицу в позиции FruitCode[temp]. Если фрукта temp в массиве availableFruits нет, то его можно просто игнорировать. Построенные маски из нелюбимых фруктов заносим в массив v, так что v[i] содержит маску, характеризующую набор фруктов из availableFruits, который не нравится i - ому другу.

В маске каждый фрукт соответствует одному биту. Поскольку фруктов не более 50, то использование типа long long (64 битового) для маски mask достаточно. Функция bits(n) вычисляет количество бит числа n.

Далее перебираем все подмножества друзей (i от 1 до1 << friendsDislikings.size()). Для каждого подмножества друзей в mask заносим подмножество фруктов, которые они не любят. Всего имеется Fcode фруктов. Если число хороших фруктов Fcode – bits(mask) не меньше k, а текущее количество друзей, характеризующееся маской i и равное bits(i), содержит больше людей чем в res, то присвоим res = bits(i). По окончании перебора всех подмножеств друзей возвращаем значение res.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <sstream>

#include <map>

using namespace std;

map<string,int> FruitCode;

vector<long long> v;

int bits(long long n)

{

int res = 0;

while(n)

n = n & (n - 1), res++;

return res;

}

class BirthdayCake

{

public:

int howManyFriends(vector<string> availableFruits,

vector<string> friendsDislikings, int k)

{

int res,i,j,Fcode;

long long mask;

string temp;

for(res = Fcode = i = 0; i < availableFruits.size(); i++)

FruitCode[availableFruits[i]] = Fcode++;

for(i = 0; i < friendsDislikings.size(); i++)

{

mask = 0;

stringstream is(friendsDislikings[i]);

while(is >> temp)

if (FruitCode.find(temp) != FruitCode.end())

mask |= 1LL << FruitCode[temp];

v.push_back(mask);

}

for(i = 1; i < (1 << friendsDislikings.size()); i++)

{

mask = 0;

for(j = 0; j < friendsDislikings.size();j++)

if (i & (1 << j)) mask |= v[j];

if ((Fcode - bits(mask) >= k) && (res < bits(i))) res = bits(i);

}

return res;

}

};